package com.tyning.newcode.jz35;

//剑指 Offer 35. 复杂链表的复制
//请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
//
//
//
//示例 1：
//
//
//
//输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
//输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
//示例 2：
//
//
//
//输入：head = [[1,1],[2,1]]
//输出：[[1,1],[2,1]]
//示例 3：
//
//
//
//输入：head = [[3,null],[3,0],[3,null]]
//输出：[[3,null],[3,0],[3,null]]
//示例 4：
//
//输入：head = []
//输出：[]
//解释：给定的链表为空（空指针），因此返回 null。
//
//
//提示：
//
//-10000 <= Node.val <= 10000
//Node.random 为空（null）或指向链表中的节点。
//节点数目不超过 1000 。
//
//
//注意：本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/
// https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/


import java.util.HashMap;
import java.util.Map;

public class Solution {

    /**
     * 方法二
     */
    HashMap<Node, Node> oldHap = new HashMap<>();

    public Node copyRandomList1(Node head) {
        Node thisNode = head;
        while (thisNode != null) {
            Node node = oldHap.get(thisNode);
            if (node == null) {
                node = new Node(thisNode.val);
                oldHap.put(thisNode, node);
            }

            if (thisNode.next != null) {
                Node next = oldHap.get(thisNode.next);
                if (next == null) {
                    next = new Node(thisNode.next.val);
                    oldHap.put(thisNode.next, next);
                }

                node.next = next;
            }

            if (thisNode.random != null) {
                Node randomNode = oldHap.get(thisNode.random);
                if (randomNode == null) {
                    randomNode = new Node(thisNode.random.val);
                    oldHap.put(thisNode.random, randomNode);
                }
                node.random = randomNode;
            }
            thisNode = thisNode.next;
        }
        return oldHap != null ? oldHap.get(head) : null;
    }

    /**
     * 方法一
     */
    Map<Node, Node> nodeNodeMap = new HashMap<>();

    public Node copyRandomList(Node head) {
        Node newHeadNode = nodeNodeMap.get(head);
        if (newHeadNode == null) {
            newHeadNode = new Node(head.val);
            nodeNodeMap.put(head, newHeadNode);
        } else {
            return newHeadNode;
        }
        if (head.next != null) {
            newHeadNode.next = this.copyRandomList(head.next);
        }
        if (head.random != null) {
            newHeadNode.random = this.copyRandomList(head.random);
        }
        return newHeadNode;
    }

    public static void main(String[] args) {

    }
}
